package com.gitee.algorithm.linear;

import java.util.Iterator;

public class SequenceList<T> implements Iterable<T> {
    //储存元素的数组
    private T[] eles;

    //记录当前顺序表中的元素个数
    private int N;

    //构造方法
    public SequenceList(int capacity) {
        //初始化数组
        this.eles = (T[]) new Object[capacity];
        this.N = 0;
    }

    //将一个线性表置为空表
    public void clear() {
        this.N = 0;
    }

    //判断当前线性表是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //获取线性表的长度
    public int length() {
        return N;
    }

    //获取指定位置的元素
    public T get(int i) {
        return eles[i];
    }

    //向线性表中添加元素
    public void insert(T t) {
        if(N==eles.length){
            relize(eles.length*2);
        }
        eles[N++] = t;
    }

    //在i元素处插入元素t
    public void insert(int i, T t) {
        //如果插入的i是最大索引，就不能插入
        if (i == eles.length) {
            System.out.println("线性表已经满了，插入失败");
        }
        //对于不合理的插入索引检测
        if (i < 0 || i > N) {
            System.out.println("不合理插入索引");
        }
        //扩容
        if(N==eles.length){
            relize(eles.length*2);
        }
        //将i索引位置空出来，并将原本i索引处及其以后元素向后移动一位
        for (int index = N; index > i; index--) {
            eles[index] = eles[index - 1];
        }
        //将t元素方到i索引
        eles[i] = t;
        //N+1
        N++;
    }

    //删除指定位置i处的元素，并返回该元素
    public T remove(int i) {
        if (i < 0 || i > N - 1) {
            throw new RuntimeException("当前要删除的元素不存在");
        }
        //缩容
        if(N==eles.length/4){
            relize(eles.length/2);
        }
        //将i索引位置空出来，将后边元素向前移动一位
        for (int index = i; index < N - 1; index++) {
            eles[index] = eles[index++];
        }
        N--;
        return eles[i];
    }

    //查找t元素第一次出现的位置
    public int indexOf(T t) {
        if (t == null) {
            throw new RuntimeException("查找的元素不合法");
        }
        for (int i = 0; i < N; i++) {
            if (eles[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }
    private class SIterator implements Iterator{
        private int cusor;
        public SIterator(){
            this.cusor=0;
        }
        @Override
        public boolean hasNext() {
            return cusor<N;
        }

        @Override
        public Object next() {
            return eles[cusor++];
        }
    }
        //线性表容量扩容
    private void relize(int newsize){
        //创建辅助数组指向原数组，将数组内元素复制到辅助数组
        T[] temp=eles;
        //创建扩容的新数组
        eles = (T[]) new Object[newsize];
        //将原数组元素添加到新数组
        for(int i=0;i<N;i++){
            eles[i]=temp[i];
        }
    }
}
